package main

func main() {

}

/*
*
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
*/
func longestValidParentheses(s string) int {
	if len(s) == 0 {
		return 0
	}
	dp := make([]int, len(s))
	dp[0] = 0
	m := 0
	for i := 1; i < len(s); i++ {
		if s[i] == '(' {
			dp[i] = 0
			continue
		}
		// 当前字符是 )
		count := dp[i-1]
		if i-count-1 >= 0 && s[i-count-1] == '(' {
			if dp[i] += dp[i-1] + 2; i-count-2 >= 0 {
				dp[i] += dp[i-count-2]
			}
		}

		m = max(m, dp[i])
	}
	return m
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}
